Browsing by Subject "Counting networks"

Now showing items 1-8 of 8

    • Article  

      A combinatorial treatment of balancing networks 

      Busch, Costas; Mavronicolas, Marios (1996)
      Balancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data structures ...
    • Conference Object  

      Contention in balancing networks resolved 

      Hadjimitsis, Leonidas; Mavronicolas, Marios (ACM, 1998)
      Counting networks have been originally presented by Aspnes et al. as a new class of distributed/coordinated data structures suitable for solving many fundamental, multi-processor coordination problems that can be expressed ...
    • Article  

      An efficient counting network 

      Busch, Costas; Mavronicolas, Marios (2010)
      We present a novel counting network construction, where the number of input wires w is smaller than or equal to the number of output wires t. The depth of our network is Θ(lg2w), which depends only on w. In contrast, the ...
    • Conference Object  

      Impact of timing on linearizability in counting networks 

      Mavronicolas, Marios; Papatriantafilou, Marina; Tsigas, Philippas (IEEE, 1997)
      Counting networks form a new class of distributed, low-contention data structures, made up of interconnected balancers and are suitable for solving a variety of multiprocessor synchronization problems that can be expressed ...
    • Article  

      Notes on sorting and counting networks 

      Hardavellas, N.; Karakos, D.; Mavronicolas, Marios (1993)
      Implementing counting networks on shared-memory multiprocessor machines often incurs a performance penalty proportional to the depth of the networks and the extent to which concurrent processors access the same memory ...
    • Article  

      Sequentially consistent versus linearizable counting networks 

      Mavronicolas, Marios; Merritt, M.; Taubenfeld, G. (2008)
      We compare the impact of timing conditions on implementing sequentially consistent and linearizable counters using (uniform) counting networks in distributed systems. For counting problems in application domains which do ...
    • Conference Object  

      Strength of counting networks 

      Busch, Costas; Mavronicolas, Marios (1996)
      This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each ...
    • Article  

      Supporting increment and decrement operations in balancing networks 

      Aiello, W.; Busch, Costas; Herlihy, M.; Mavronicolas, Marios; Shavit, N.; Touitou, D. (1999)
      Counting networks are a class of distributed data structures that support highly concurrent implementations of shared Fetch&Increment counters. Applications of these counters include shared pools and stacks, load balancing, ...